package com.wkh.datastructure.ReverseLinkedList;


//反转链表----方法三 ----> 递归实现
public class demo3 {
    public static void main(String[] args) {
        ListNode node4 = new ListNode(null, 4);
        ListNode node3 = new ListNode(node4, 3);
        ListNode node2 = new ListNode(node3, 2);
        ListNode node1= new ListNode(node2, 1);
        ListNode reverse = reverse(node1);
    }

    //递归函数
    private static ListNode reverse(ListNode node1) {
        //空链表或查到了最后一个节点
        if (node1 == null || node1.next == null){
            return node1;
        }
        ListNode last = reverse(node1.next);
        node1.next.next = node1;
        node1.next = null;
        return last;
    }

    static class List{
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }
        public void addFirst(ListNode first){
            first.next = head;
            head = first;
        }
        public ListNode removeFirst(){
            ListNode first = this.head;
            if (first != null){
                head = first.next;
            }
            return first;
        }
    }
}
